package com.dexter.year2023.charpter1_linkedlist.level2.topic2_2回文序列;

import java.util.Stack;

import com.dexter.year2023.charpter1_linkedlist.level1.Demo1.Node;

import static com.dexter.year2023.charpter1_linkedlist.level1.Demo1.initLinkedList;

/**
 * LeetCode 234. 回文链表
 * https://leetcode.cn/problems/palindrome-linked-list/
 * <p>
 * 给你一个单链表的头结点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
 * <p>
 * 示例 1：
 * 输入：head = [1,2,2,1]
 * 输出：true
 * 示例 2：
 * 输入：head = [1,2]
 * 输出：false
 * <p>
 * 提示：
 * 链表中结点数目在范围[1, 105] 内
 * 0 <= Node.val <= 9
 * <p>
 * 进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
 *
 * @author Dexter
 */
public class IsPalindromic {
    /**
     * 思路：
     * 法1：放进数组，从两端向中间对比，被视为逃避数组（不好）
     * 法2：全部入栈，出栈时对比
     * 法3：遍历链表，入栈一半元素，出栈对比
     * 法4：（优化2、3）遍历链表的同时入栈元素，出栈一半元素
     * 法5：反转链表，newList与oldList对比
     * 法6：（优化5）遍历链表，反转一半
     * 法7：快慢指针，同步时对比
     * 法8：（进阶6）遍历链表，用递归 反转一半
     *
     * @param args
     */
    public static void main(String[] args) {
        int[] a = {1, 2, 3, 4, 4, 3, 2, 1};
        Node head = initLinkedList(a);
        int testMethod = 4;
        boolean res = false;
        switch (testMethod) {
            case 1:
                // 法2：全部入栈
                res = isPalindromeByAllStack(head);
                break;
            case 2:
                // 法4：遍历入栈，一半出栈
                res = isPalindromeByHalfStack(head);
                break;
            case 3:
                // 法7：快慢指针
                res = isPalindromeByTwoPoints(head);
                break;
            case 4:
                // 法x：递归
                res = isPalindromeByRe(head);
                break;
            default:
                System.out.println("测试方法超出范围");
                break;
        }
        System.out.println("是否为回文序列：" + (res ? "是" : "否"));
    }

    /**
     * 法2：全部入栈，遍历两次 （需要考虑时间复杂度、空间复杂度）
     *
     * @param head
     * @return
     */
    private static boolean isPalindromeByAllStack(Node head) {
        // 判空
        if (head == null || head.next == null) {
            return true;
        }
        // 初始化
        Stack<Integer> stack = new Stack<>();
        // 入栈
        Node cur = head;
        while (cur != null) {
            stack.push(cur.val);
            cur = cur.next;
        }
        // 出栈
        while (head != null) {
            if (head.val != stack.pop()) {
                // 从头开始遍历，与出栈元素不同
                return false;
            }
            head = head.next;
        }
        return true;
    }

    /**
     * 法4：遍历获取长度，将一半数据【出栈】
     *
     * @param head
     * @return
     */
    private static boolean isPalindromeByHalfStack(Node head) {
        // 判空
        if (head == null || head.next == null) {
            return true;
        }
        // 初始化
        Stack<Integer> stack = new Stack<>();
        Node cur = head;
        int len = 0;
        // 遍历，入栈
        while (cur != null) {
            stack.push(cur.val);
            len++;
            cur = cur.next;
        }
        // 长度除以2
        len >>= 1;
        // 出栈
        while (len-- > 0) {
            if (head.val != stack.pop()) {
                return false;
            }
            head = head.next;
        }
        return true;
    }

    /**
     * 法7：双指针 fast slow 与 pre 对比
     *
     * @param head
     * @return
     */
    private static boolean isPalindromeByTwoPoints(Node head) {
        // 判空
        if (head == null || head.next == null) {
            return true;
        }
        // 双指针初始化
        Node slow = head, fast = head;
        // 判断指针初始化
        Node pre = head, prepre = null;
        // 快、慢走
        while (fast != null && fast.next != null) {
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
            // 调整pre链表的方向，往 4 -> 3 -> 2 -> 1 -> null 的方向去
            pre.next = prepre;
            prepre = pre;
        }
        // 奇数个数，循环结束时，fast在尾结点，slow在中间位置，为了让slow向后挪到第一个回文判断的位置 5 去 4
        if (fast != null) {
            slow = slow.next;
        }
        // 同步走
        while (pre != null && slow != null) {
            // pre回头，slow往前
            if (pre.val != slow.val) {
                return false;
            }
            pre = pre.next;
            slow = slow.next;
        }
        return true;
    }


    static Node temp;

    /**
     * 法x：递归，temp一直走正向，head走到尾再反向将temp.val与head.val比较
     *
     * @param head
     * @return
     */
    private static boolean isPalindromeByRe(Node head) {
        temp = head;
        return check(head);
    }

    private static boolean check(Node head) {
        if (head == null) {
            return true;
        }
        boolean res = check(head.next) && (temp.val == head.val);
        // 等head反向了，temp才有变化，之前都是在check递归里
        temp = temp.next;
        return res;
    }
}
